原文題目
Given the root of a binary tree, return the inorder traversal of its nodes' values.

題目摘要

1. 問題描述: 給定一個二元樹的根節點，要求返回其節點值的中序遍歷順序。
2. 輸入: 二元樹的根節點TreeNode root。
3. 輸出: 包含節點值的列表，按中序遍歷順序排列。

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]
Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]
Explanation:

Example 3:

Input: root = []
Output: []

Example 4:

Input: root = [1]
Output: [1]

解題思路一

1. 理解中序走訪的順序：

   中序走訪順序是「左子樹 -> 根節點 -> 右子樹」。

2. 使用堆疊儲存節點：

   我們將當前節點（從根節點開始）儲存到堆疊中，並不斷向左子樹走訪直到遇到 null。每遇到一個非空節點，我們將它推入堆疊。

3. 處理當前節點：

   當左子樹走訪到底後（即 currentNode == null），從堆疊中彈出節點，將該節點的值加入結果列表中，然後移動到右子樹。

4. 重複過程：

   重複以上過程，直到所有節點都被處理完，即堆疊為空且當前節點為 null。

5. 回傳結果：

   最後返回包含節點值的列表，即中序走訪的結果。

程式碼一

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode currentNode = root;

        //while(!(currentNode==null&&stack.isEmpty)){}一樣意思寫法
        while(currentNode != null || !stack.isEmpty()){
            //左子樹先一路走到底
            while(currentNode != null){
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            //當左子樹到底時將最後一個進stack的節點移至結果陣列儲存再往右子樹開始找
            currentNode = stack.pop();
            result.add(currentNode.val);
            currentNode = currentNode.right;
        }
        return result;
    }
}

解題思路二

1. 創建結果列表：

   使用一個列表 result 來存儲中序走訪的結果，即按照「左子樹 → 根節點 → 右子樹」的順序除去節點值。

2. 開始中序走訪：

   使用輔助方法 makeInorder 來遞迴地遍歷樹的每個節點，並將遍歷結果添加到結果列表中。

3. 處理空節點：

   當節點為 null 時，直接返回，因為空節點不需要進一步處理。

4. 遞迴遍歷左子樹、處理當前節點及遞迴遍歷右子樹：

   • 遞迴使用 makeInorder 方法遍歷左子樹。
   • 遍歷完左子樹後，將當前節點的值添加到結果列表中。
   • 遞迴調用 makeInorder 方法遍歷右子樹。

5. 回傳結果列表：

   遍歷完成後，返回結果列表 result。

   對左子樹和右子樹重複相同的步驟，直到走訪完所有節點。

程式碼二

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        //設立一個列表來存儲中序走訪的結果
        List<Integer> result = new ArrayList<>();

        makeInorder(root, result); //開始中序走訪
        return result; //走訪完成則回傳結果列表       
    }

    private void makeInorder(TreeNode node, List<Integer> result) {
        //如果當前節點為null則返回
        if (node == null) {
            return;
        }
        makeInorder(node.left, result); //遞迴遍歷左子樹
        result.add(node.val); //直到不能再遍歷左子樹，將當前節點的值加到結果列表中
        makeInorder(node.right, result); //遞迴遍歷右子樹
    }    
}

結論
這題我和我的組員分別使用了兩種解法，第一種是迭代解法，第二種則是遞迴解法。迭代解法利用堆疊有效地處理了樹的深度，避免了遞迴可能帶來的空間消耗。遞迴解法透過輔助函數來簡化整個過程，使程式碼更為清晰易懂。藉由練習這題題目不僅讓我加深了對二元樹中序遍歷的理解，也透過小組討論讓我認識了不同解法及其特點。